{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "b4683f40",
   "metadata": {},
   "source": [
    "# 何为递归？\n",
    "1. 递归是解决问题的一种方法，它将问题不断地分成更小的子问题，直到子问题可以用普通的方法解决。\n",
    "2. 通常，递归会使用一个不停调用自己的函数\n",
    "\n",
    "# 递归算法三原则\n",
    "1. 必须有基本情况\n",
    "2. 必须改变其状态并向基本情况靠近\n",
    "3. 必须递归地调用自己"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "efdf613e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\n该def的核心在于\\n1.listsum函数接受的参数是活动的              # \\n2.listsum函数在return时，调用了一次自己      #调用自己\\n3.listsum在调用自己时，给的参数是越来越小的  #分割任务,%gui变自身状况并向基本情况靠近\\n'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 1.递归求和\n",
    "\n",
    "def listsum(numlist):\n",
    "    if len(numlist) ==1:\n",
    "        return numlist[0]\n",
    "    else:\n",
    "        return numlist[0] + listsum(numlist[1:])   \n",
    "\n",
    "listsum([1,2,3])\n",
    "\n",
    "\"\"\"\n",
    "该def的核心在于\n",
    "1.listsum函数接受的参数是活动的              # \n",
    "2.listsum函数在return时，调用了一次自己      #调用自己\n",
    "3.listsum在调用自己时，给的参数是越来越小的  #分割任务,%gui变自身状况并向基本情况靠近\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "68cddfbe",
   "metadata": {},
   "source": [
    "# 栈stack与栈帧Stack Frame\n",
    "1. 从关系上看：栈帧是栈的组成单元，栈里面的元素都是以栈帧的形式存储。\n",
    "2. 从逻辑上看：栈帧就是一个函数执行的环境：函数参数、函数的局部变量、函数执行完后返回到哪里等等。\n",
    "\n",
    "# 栈帧的意义\n",
    "\n",
    "栈帧来处理该函数的局部变量。当函数返回时，返回值就在栈的顶端，以供调用者访问。\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d7ead699",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "###### 用栈帧来实现循环 #########\n",
    "\n",
    "#rStack = Stack()  \n",
    "\n",
    "def toStr(n,base):               \n",
    "    c = \"0123456789ABCDEF\"\n",
    "    if n<base:\n",
    "        rStack.push(c[n])        # 在计算一列数之和的例子中，可以认为栈中的返回值取代了累加变量。\n",
    "    else:\n",
    "        rStack.push(c[n%base])   # 在计算一列数之和的例子中，可以认为栈中的返回值取代了累加变量。[就不需要return时再调用自己了]\n",
    "        toStr(n//base,base)      # 仅调用自己 实现递归\n",
    "\n",
    "###### 不用栈实现循环 #########\n",
    "def listsum(numList):           # 用 return +调用自己 实现递归\n",
    "    if len(numList) == 1:\n",
    "        return numList[0]\n",
    "    else:\n",
    "        return numList[0]+ listsum(numList[1:])   #\n",
    "\n",
    "    \n",
    "# 两个函数的区别\n",
    "# 1.栈帧函数不返回值，但在函数中调用自己实现递归，它是直接操作类\n",
    "# 2.原递归函数返回时，调用自己，并返回一个记录值+递归值【从而实现递归】"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b7057bac",
   "metadata": {},
   "source": [
    "# 复杂的递归问题——汉诺塔给我的启发\n",
    "递归体 = 递归体部分 + 可计算部分 = n个0 + m个可计算部分\n",
    "\n",
    "\n",
    "1. **要把五个块从1移到3** = **把四个块从1移到2** + 第五块从1移到3 + **把四个块从2移到3** [加粗部分就是递归体i]\n",
    "2. 一号柱：frompole；二号柱：withpole；三号柱：topole；\n",
    "3. 其中递归1的需要移到个数n；递归体2为n-1；递归体3为n-1；\n",
    "4. 其中递归1的frompole（起始点） =递归2的frompole（起始点） = 递归3的withpole（起始点）\n",
    "5. 其中递归1的topole（起始点） =递归2的withpole（起始点） = 递归3的topole（起始点）\n",
    "6. 其中递归1的withpole（起始点） =递归2的topole（起始点） = 递归3的frompole（起始点）\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "182afcf4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 汉罗塔\n",
    "def mt(h,frompole,topole,withpole): #递归变量h,frompole,topole,withpole  # h是逼近变量\n",
    "    if h >=1:\n",
    "        mt(h-1,frompole,withpole,topole) \n",
    "        moveDisk(frompole,topole)\n",
    "        mt(h-1,withpole,topole,frompole)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1ba196ed",
   "metadata": {},
   "source": [
    "# 递归问题——用递归拟合动态规划-解决找零用银币最少问题\n",
    "- 动态规划：在解决找零问题时，动态规划算法会从1分找零开始，然后系统地一直计算到所需的找零金额。这样做可以保证在每一步都已经知道任何小于当前值的找零金额所需的最少硬币数。\n",
    "- 贪心算法：使用尽可能多的硬币，然后尽可能多地使用面值第2大的硬币。这种方法叫作贪婪算法——试图最大程度地解决问题。\n",
    "    - 贪心算法缺点：不一定获得最优解决\n",
    "- 用递归拟合动态规划\n",
    "    1. 首先确定基本情况【钱金额与硬币的面值相同，那么只需找1枚硬币即可】\n",
    "    2. 多种选择：1枚1分的硬币加上找零金额减去1分之后所需的硬币；... 1枚25分的硬币加上找零金额减去25分之后所需的硬币。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "d33ac1e9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 很复杂需要慢慢理解\n",
    "def r(cl,change):\n",
    "    mincoins = change \n",
    "    if change in cl:\n",
    "        return 1\n",
    "    else:\n",
    "        for i in [c for c in cl if c<= change]:  # 只选面值小于余额的银币列表\n",
    "            numcoins = 1 + r(cl,change-i)        #  当前递归链路所用硬币数，【递归体】\n",
    "            if numcoins < mincoins:              # 比较历史最小硬币数，与当前链路银币数\n",
    "                mincoins = numcoins              # 记录两者最小值，作为历史最小硬币数\n",
    "    return mincoins\n",
    "r([1,5,10,25],50)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ccaa0f85",
   "metadata": {},
   "source": [
    "# 递归-小结\n",
    "\n",
    "1. 判断一个问题是否能够用递归完成，要看该问题是否满足递归三要素\n",
    "2. 要写递归前，先实现问题的基本情况；再写其他情况\n",
    "3. 递归算法再某些情况下可替代，并且递归在该情况下不一定是最优算法、\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fa0a304b",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
